package com.practice.zuocy.base.class12;

/*
 *什么暴力递归可以继续优化？
 * （1）有重复调用一个子问题的解，这种递归可以优化
 * （2）如果每一个子问题都是不同的解，无法优化也不用优化
 */

/*
 *暴力递归和动态规划的关系
 * （1）某一个暴力递归，有解的重复调用，就可以把这个暴力递归优化成动态规划
 * （2）任何一个动态规划问题，都一定对应着某一个有解的重复调用的暴力递归；但不是所有的暴力递归，都一定对应着动态规划
 */

/*
 * 面试题和动态规划的关系
 * （1）解决一个问题，可能有很多尝试方法，可能在很多种尝试方法中，又有若干个尝试方法有动态规划的方式
 * （2）一个问题，可能有若干种动态规划的解法
 */

/*
 * 如何找到某个问题的动态规划方式？
 * （1）设计暴力递归：重要原则+4种尝试模型！重点！
 * （2）分析有没有重复解：套路解决
 * （3）用记忆化搜索 --> 用严格表结构实现动态规划：套路解决
 * （4）看看能否继续优化：套路解决
 */

/*
 * 面试中设计暴力递归过程的原则
 * （1）每一个可变参数的类型，一定不要比int类型更加复杂
 * （2）原则（1）可以违反，让类型突破到一维线性结构，那必须是唯一可变参数
 * （3）如果发现原则（1）被违反，但不违反原则（2），只需要做到记忆化搜索即可
 * （4）可变参数的个数，能少则少
 */

/*
 * 知道了面试中设计暴力递归过程的原则，然后呢？
 * （1）一定要逼自己找到不违反原则情况下的暴力尝试！
 * （2）如果你找到的暴力递归，不符合原则，马上舍弃！找新的！
 * （3）如果某个题目突破了设计原则，一定极难极难，面试中出现概率低于5%！
 */

/*
 * 如何分析有没有重复解
 * （1）列出调用过程，可以只列出前几层
 * （2）有没有重复解，已看便知
 */

/*
 * 暴力递归到动态规划的套路
 * （1）你已经有了一个不违反原则的暴力递归，而且的确存在解的重复调用
 * （2）找到哪些参数的变化会影响返回值，对每一个列出变化范围
 * （3）参数间的所有组合数量，意味着表的大小
 * （4）记忆化搜索的方法就是傻缓存，非常容易得到
 * （5）规定好严格表的大小，分析位置的依赖顺序，然后从基础填写到最终解
 * （6）对于有枚举行为的决策过程，进一步优化
 */

/*
 * 动态规划的进一步优化：
 * （1）空间压缩
 * （2）状态简化
 * （3）四边形不等式
 * 其他优化技巧略
 */


/*
 * 常见的4种尝试模型：
 * （1）从左到右的尝试模型----（例如背包问题，字符串转数字。。。）
 * （2）范围上的尝试模型------（例如一条线拿牌问题）
 * （3）多样本位置全对应的尝试模型（一个作行一个作列的尝试模式）----（最长公共子序列，子串等等）
 * （4）寻找业务限制的尝试模式（剪枝）
 */


/**
 * 【题目】：（TODO：从左往右尝试模式）
 * 假设有排成一行的 N 个位置，记为1~N，N一定大于或等于2。
 * 开始时机器人在其中的start位置上(start一定是1~N中的一个)，
 * 机器人可以往左走或者往右走，
 * 如果机器人来到1位置， 那么下一步只能往右来到2位置；
 * 如果机器人来到N位置，那么下一步只能往左来到N-1位置。
 * 规定机器人必须走K步，最终能来到end位置(end也一定是1~N中的一个)的方法有多少种。
 * 给定四个参数 N、start、K、end，返回方法数。
 * 【举例】:
 * N=5, start=2, K=3, end=3：
 * 上面的参数代表所有位置为 1 2 3 4 5。机器人最开始在 2 位置上，必须经过 3 步，最后到达 3 位置。走的方法只有如下 3 种:
 * （1）从2到1，从1到2，从2到3
 * （2）从2到3，从3到2，从2到3
 * （3）从2到3，从3到4，从4到3
 * 所以返回方法数 3。
 * N=3, start=1, K=3, end=3：
 * 上面的参数代表所有位置为 1 2 3。机器人最开始在 1 位置上，必须经过 3 步，最后到达 3位置。怎么走也不可能，所以返回方法数 0。
 */
public class Code01_RobotWalk {

	public static int ways1(int N, int M, int K, int P) {
		// 参数无效直接返回0
		if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
			return 0;
		}
		// 总共N个位置，从M点出发，还剩K步，返回最终能达到P的方法数
		return walk(N, M, K, P);
	}

	// N : 位置为1 ~ N，固定参数
	// cur : 当前在cur位置，可变参数
	// rest : 还剩res步没有走，可变参数
	// P : 最终目标位置是P，固定参数
	// 该函数的含义：只能在1~N这些位置上移动，当前在cur位置，走完rest步之后，停在P位置的方法数作为返回值返回
	public static int walk(int N, int cur, int rest, int P) {
		// 如果没有剩余步数了，当前的cur位置就是最后的位置
		// 如果最后的位置停在P上，那么之前做的移动是有效的
		// 如果最后的位置没在P上，那么之前做的移动是无效的
		if (rest == 0) {
			return cur == P ? 1 : 0;
		}
		// 如果还有rest步要走，而当前的cur位置在1位置上，那么当前这步只能从1走向2
		// 后续的过程就是，来到2位置上，还剩rest-1步要走
		if (cur == 1) {
			return walk(N, 2, rest - 1, P);
		}
		// 如果还有rest步要走，而当前的cur位置在N位置上，那么当前这步只能从N走向N-1
		// 后续的过程就是，来到N-1位置上，还剩rest-1步要走
		if (cur == N) {
			return walk(N, N - 1, rest - 1, P);
		}
		// 如果还有rest步要走，而当前的cur位置在中间位置上，那么当前这步可以走向左，也可以走向右
		// 走向左之后，后续的过程就是，来到cur-1位置上，还剩rest-1步要走
		// 走向右之后，后续的过程就是，来到cur+1位置上，还剩rest-1步要走
		// 走向左、走向右是截然不同的方法，所以总方法数要都算上
		return walk(N, cur + 1, rest - 1, P) + walk(N, cur - 1, rest - 1, P);
	}






	public static int waysCache(int N, int M, int K, int P) {
		// 参数无效直接返回0
		if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
			return 0;
		}

		int[][] dp = new int[N+1][K+1];
		for(int row = 0; row <= N; row++) {
			for(int col = 0; col <= K; col++) {
				dp[row][col] = -1;
			}
		}
		return walkCache(N, M, K, P,dp);
	}

	// HashMap<String, Integer>   (19,100)  "19_100"
	// 我想把所有cur和rest的组合，返回的结果，加入到缓存里
	public static int walkCache(int N, int cur, int rest, int P, int[][] dp) {
		if(dp[cur][rest] != -1) {
			return dp[cur][rest];
		}
		if (rest == 0) {
			dp[cur][rest] = cur == P ? 1 : 0;
			return dp[cur][rest];
		}
		if (cur == 1) {
			dp[cur][rest] = walkCache(N, 2, rest - 1, P, dp);
			return dp[cur][rest];
		}
		if (cur == N) {
			dp[cur][rest] =walkCache(N, N - 1, rest - 1, P,dp);
			return dp[cur][rest];
		}
		dp[cur][rest] = walkCache(N, cur + 1, rest - 1, P,dp)
				+ walkCache(N, cur - 1, rest - 1, P, dp);
		return dp[cur][rest];
	}











	public static int ways2(int N, int M, int K, int P) {
		// 参数无效直接返回0
		if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
			return 0;
		}
		int[][] dp = new int[K + 1][N + 1];
		dp[0][P] = 1;
		for (int i = 1; i <= K; i++) {
			for (int j = 1; j <= N; j++) {
				if (j == 1) {
					dp[i][j] = dp[i - 1][2];
				} else if (j == N) {
					dp[i][j] = dp[i - 1][N - 1];
				} else {
					dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
				}
			}
		}
		return dp[K][M];
	}

	public static int ways3(int N, int M, int K, int P) {
		// 参数无效直接返回0
		if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
			return 0;
		}
		int[] dp = new int[N + 1];
		dp[P] = 1;
		for (int i = 1; i <= K; i++) {
			int leftUp = dp[1];// 左上角的值
			for (int j = 1; j <= N; j++) {
				int tmp = dp[j];
				if (j == 1) {
					dp[j] = dp[j + 1];
				} else if (j == N) {
					dp[j] = leftUp;
				} else {
					dp[j] = leftUp + dp[j + 1];
				}
				leftUp = tmp;
			}
		}
		return dp[M];
	}

	// ways4是你的方法
	public static int ways4(int N, int M, int K, int P) {
		if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
			return 0;
		}
		return process(N, 0, P, M, K);
	}

	// 一共N个位置，从M点出发，一共只有K步。返回走到位置j，剩余步数为i的方法数
	public static int process(int N, int i, int j, int M, int K) {
		if (i == K) {
			return j == M ? 1 : 0;
		}
		if (j == 1) {
			return process(N, i + 1, j + 1, M, K);
		}
		if (j == N) {
			return process(N, i + 1, j - 1, M, K);
		}
		return process(N, i + 1, j + 1, M, K) + process(N, i + 1, j - 1, M, K);
	}

	// ways5是你的方法的dp优化
	public static int ways5(int N, int M, int K, int P) {
		if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
			return 0;
		}
		int[][] dp = new int[K + 1][N + 1];
		dp[K][M] = 1;
		for (int i = K - 1; i >= 0; i--) {
			for (int j = 1; j <= N; j++) {
				if (j == 1) {
					dp[i][j] = dp[i + 1][j + 1];
				} else if (j == N) {
					dp[i][j] = dp[i + 1][j - 1];
				} else {
					dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j - 1];
				}
			}
		}
		return dp[0][P];
	}

	public static void main(String[] args) {
		System.out.println(ways1(7, 4, 9, 5));
		System.out.println(ways2(7, 4, 9, 5));
		System.out.println(ways3(7, 4, 9, 5));
		System.out.println(ways4(7, 4, 9, 5));
		System.out.println(ways5(7, 4, 9, 5));
	}

}
